By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 30, Issue 2, pp. 347-687

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Message Multicasting in Heterogeneous Networks

Amotz Bar-Noy, Sudipto Guha, Joseph (Seffi) Naor, and Baruch Schieber

pp. 347-358

BibTeX  Abstract Full Text:  PDF

Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras

Clifford Bergman and Giora Slutzki

pp. 359-382

BibTeX  Abstract Full Text:  PDF

An Algorithm for Heilbronn's Problem

Claudia Bertram--Kretzberg, Thomas Hofmeister, and Hanno Lefmann

pp. 383-390

BibTeX  Abstract Full Text:  PDF

Nonmalleable Cryptography

Danny Dolev, Cynthia Dwork, and Moni Naor

pp. 391-437

BibTeX  Abstract Full Text:  PDF

Time and Space Lower Bounds for Nonblocking Implementations

Prasad Jayanti, King Tan, and Sam Toueg

pp. 438-456

BibTeX  Abstract Full Text:  PDF

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces

Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani

pp. 457-474

BibTeX  Abstract Full Text:  PDF

When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

Luca Trevisan

pp. 475-485

BibTeX  Abstract Full Text:  PDF

Self-Stabilization by Counter Flushing

George Varghese

pp. 486-510

BibTeX  Abstract Full Text:  PDF

The Power of Migration in Multiprocessor Scheduling of Real-Time Systems

Gilad Koren, Emanuel Dar, and Amihood Amir

pp. 511-527

BibTeX  Abstract Full Text:  PDF

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching

Joseph Cheriyan and Ramakrishna Thurimella

pp. 528-560

BibTeX  Abstract Full Text:  PDF

Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions

Timothy M. Chan

pp. 561-575

BibTeX  Abstract Full Text:  PDF

A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, and Martin Strauss

pp. 576-601

BibTeX  Abstract Full Text:  PDF

Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, and Hing-Fung Ting

pp. 602-624

BibTeX  Abstract Full Text:  PDF

Constructive, Deterministic Implementation of Shared Memory on Meshes

Andrea Pietracaprina, Geppino Pucci, and Jop F. Sibeyn

pp. 625-648

BibTeX  Abstract Full Text:  PDF

How to Make a Square Grid Framework with Cables Rigid

Harold N. Gabow and Tibor Jordán

pp. 649-680

BibTeX  Abstract Full Text:  PDF

On a Conjecture by Coffman, Flatto, and Wright on Stochastic Machine Minimization

Nah-Oak Song and Demosthenis Teneketzis

pp. 681-687

BibTeX  Abstract Full Text:  PDF